package club.xiaojiawei.back;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/20/22 10:21 PM
 * @question 40. 组合总和 II
 * @description 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * 注意：解集不能包含重复的组合。
 */
public class CombinationSum240 {

    public static void main(String[] args) {
        CombinationSum240 test = new CombinationSum240();
        List<List<Integer>> result = test.combinationSum22(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
        System.out.println(result);
    }

    /**
     * 排序+递归
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        recursion(candidates, target, 0);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();

    List<Integer> temp = new ArrayList<>();

    int count = 0;

    public void recursion(int[] candidates, int target, int startIndex){
        for (int i = startIndex; i < candidates.length && count + candidates[i] <= target; i++){
            if (i != startIndex && candidates[i] == candidates[i - 1]){
                continue;
            }
            temp.add(candidates[i]);
            count += candidates[i];
            if (count == target){
                result.add(new ArrayList<>(temp));
                count -= temp.remove(temp.size() - 1);
                return;
            }else {
                recursion(candidates, target, i + 1);
                count -= temp.remove(temp.size() - 1);
            }
        }
    }

    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();

    /**
     * 官方-递归回溯
     * 时间复杂度：O(2^n * n)
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum22(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }

    /**
     * 民间- 排序（自己写归并排序，不用java自带的排序）+递归
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum23(int[] candidates, int target) {
        doSort(candidates, 0, candidates.length - 1);
        List<List<Integer>> result = new ArrayList<>();
        doCal(candidates, target, 0, 0, new ArrayList<>(), result);
        return result;


    }
    public void doCal(int[] ar, int target, int startIndex, int sum, List<Integer> list, List<List<Integer>> result){
        if(sum == target){
            List<Integer> newList = new ArrayList<>(list);
            result.add(newList);
            return;
        }
        int pre = 0 ;
        for(int i = startIndex; i < ar.length && sum + ar[i] <= target ; i ++){
            if(i != startIndex && pre == ar[i]){
                continue;
            }
            pre = ar[i];
            list.add(ar[i]);
            doCal(ar, target, i + 1,sum + ar[i], list, result);
            list.remove(list.size() - 1);
        }
    }




    public  void doSort(int[] ar, int l, int r){
        if(l < r){
            int mid = l + (r - l)/2;
            doSort(ar,l,mid);
            doSort(ar,mid+1,r);
            Merge(ar,l,mid,r);
        }
    }

    public  void Merge(int[] ar, int l, int mid, int r){
        // 合并两个有序数组
        int[] help = new int[r - l + 1];
        int le = l;
        int ri = mid + 1;
        int ind = 0;
        while(le <= mid && ri <= r){
            help[ind++] = ar[le] > ar[ri]? ar[ri++]:ar[le++];
        }
        while(le <= mid){
            help[ind++] = ar[le++];
        }
        while(ri <= r){
            help[ind++] = ar[ri++];
        }
        ind = 0;
        for(int i = l;i<=r;i++){
            ar[l++] = help[ind++];
        }
    }
}
